Routing engines are implemented in data communication networks to make routing decisions on packets received from network devices. Routing decisions are generally made by comparing, for a match, identifiers encoded in the inbound packets with identifiers stored in a memory element associated with the routing engine. Conventionally, such associative comparisons were performed in software-only routing engines which employed routing software in a central processing unit (CPU) to compare the inbound identifiers with identifiers stored in a random access memory (RAM). However, dramatic increases in the amount of internet traffic eventually created a need for routing speeds beyond the capability of many software-only routing engines. This need gave rise to hardware routing engines which use custom circuitry to perform associative comparisons. One type of hardware routing engine performs associative comparisons using a content addressable memory (CAM). A different type of hardware routing engine performs associative comparisons using RAM.
CAM-based hardware routing engines have advantages in terms of the speed at which CAM entries can be accessed. CAM allows an inbound identifier to be compared simultaneously with all entries in the CAM, guaranteeing that any matching identifier will be revealed on the first attempt. However, when implementing a hardware routing engine, consideration must be given not only to routing speed, but also to the extent to which shared resources are required to achieve the routing speed, the number of entries required and the cost of implementation. CAM generally has a complex internal architecture which is expensive to implement and provides limited storage capacity. Thus, RAM-based hardware routing engines have been developed in an attempt to achieve routing speeds comparable to CAM-based hardware routing engines while performing associative comparisons in generally less expensive and larger capacity RAM.
A considerable technical challenge facing RAM-based hardware routing engine designers is how to work-around the access limitation of RAM. RAM allows an inbound identifier to be compared against only one RAM entry at a time. Thus, when searching RAM for a match for an inbound identifier, an orderly approach to accessing entries must be taken in order to avoid unacceptably slow routing speeds. One orderly approach involves reducing the inbound identifiers to a bounded set of numerically-related pointers using a hashing algorithm.
As implemented in a hardware routing engine, a hashing algorithm reduces each identifier to a pointer which includes only the bits from bit positions that the algorithm has determined are the most effective at distinguishing identifiers from one another. Each pointer is used to write its associated identifier at a RAM index which matches (or is numerically-related to) the pointer. Assuming that each pointer reduced in this manner has at least one bit which distinguishes it from previously reduced pointers, a condition called a "perfect hash", each inbound identifier on which a routing decision must be made may then be reduced to a pointer using the same hashing algorithm and used to read the identifier at the RAM index which matches (or is numerically-related to) the pointer to reveal any matching identifier on the first attempt. Accordingly, under perfect or near perfect hash conditions, speeds approximating CAM speeds may be realized in a memory substantially larger than a CAM and at a fraction of the cost. Of course, to the extent the hashing algorithm is imperfect, pointers reduced from different identifiers may not retain distinguishing bits and may point to the same RAM index. This undesirable condition is generally addressed by writing the different identifiers having indistinguishable pointers to RAM as entries in the same linked list, or "bucket", which must be read from one-entry-at-a-time until a matching identifier is found.
While RAM-based hardware routing engines as generally described above have been implemented, there remains a need for an efficient RAM-based hardware routing engine that fulfills the basic promise of achieving and sustaining routing speeds that approximate CAM speeds. One reason this need has remained unmet is that RAM-based hardware routing engines have typically employed static hashing algorithms which, regardless of how perfect at the outset, have failed to dynamically adapt to changing patterns of bit position distinctiveness in order to retain their level of quality over time. This inability to dynamically adapt has caused buckets to fill-up with large numbers of entries over a sustained period of operation and, therefore, resulted in increasingly deteriorating routing speeds.
Furthermore, known RAM-based hardware routing engines are not believed to have provided extended recursive look-ups. In large and high-traffic networks, it is often desirable to base routing decisions on more than one matching identifier. Thus, a more complete RAM-based hardware routing solution would include a means, if an associative comparison results in a match and another associative comparison is indicated, for automatically initiating and performing the indicated associative comparison.
Thus, there is a need for a RAM-based hardware routing engine which sustains approximately CAM speeds over time while retaining the cost and size advantages of RAM-based routing engines. There is also a need for a RAM-based hardware routing engine which has an extended recursive look-up capability.